1 Abstract

The muHVT package is a collection of R functions to facilitate building topology preserving maps for rich multivariate data. Tending towards a big data preponderance, a large number of rows. A collection of R functions for this typical workflow is organized below :

1. Data Compression: Vector quantization (VQ), HVQ (hierarchical vector quantization) using means or medians. This step compresses the rows (long data frame) using a compression objective

2. Data Projection: Dimension projection of the compressed cells to 1D,2D and 3D with the Sammons Non-linear Algorithm. This step creates topology preserving map (also called as embedding) coordinates into the desired output dimension .

3. Tessellation: Create cells required for object visualization using the Voronoi Tessellation method, package includes heatmap plots for hierarchical Voronoi tessellations (HVT). This step enables data insights, visualization, and interaction with the topology preserving map. Useful for semi-supervised tasks

4. Prediction: Scoring new data sets and recording their assignment using the map objects from the above steps, in a sequence of maps if required

2 Data Understanding

In this vignette, we will use the Prices of Personal Computers dataset. This dataset contains 6261 observations and 6 features. The dataset observes the price from 1993 to 1995 of 486 personal computers in the US. The variables are price, speed, hd, ram, screen and ads.

Here, we load the training and the testing dataset.

set.seed(240)
# Load data from csv files
trainComputers <- read.csv("https://raw.githubusercontent.com/Mu-Sigma/muHVT/dev/vignettes/sample_dataset/trainComputers.csv")
testComputers <- read.csv("https://raw.githubusercontent.com/Mu-Sigma/muHVT/dev/vignettes/sample_dataset/testComputers.csv")

Let’s have a look at the scaled training dataset containing 5008 data points

# Quick peek
trainComputers <- scale(trainComputers) 
metric_list <- colnames(trainComputers)
scale_attr <- attributes(trainComputers)

trainComputers <- trainComputers %>% as.data.frame()
trainComputers1 <- round(trainComputers,4)
Table(head(trainComputers1))

Now let us check the structure of the training data and analyse its summary.

str(trainComputers)
#> 'data.frame':    5008 obs. of  6 variables:
#>  $ price : num  -1.297 -0.8 -1.136 -0.709 1.721 ...
#>  $ speed : num  -1.195 -0.783 -1.195 -1.195 -0.783 ...
#>  $ hd    : num  -1.3136 -1.2898 -0.8854 -0.8854 -0.0767 ...
#>  $ ram   : num  -0.718 -1.108 -0.718 0.063 1.624 ...
#>  $ screen: num  -0.615 -0.615 0.549 -0.615 -0.615 ...
#>  $ ads   : num  -2.39 -2.39 -2.39 -2.39 -2.39 ...

summary(trainComputers)
#>      price             speed               hd                ram          
#>  Min.   :-2.2216   Min.   :-1.1954   Min.   :-1.31361   Min.   :-1.10781  
#>  1st Qu.:-0.7520   1st Qu.:-0.7834   1st Qu.:-0.68562   1st Qu.:-0.71755  
#>  Median :-0.1276   Median : 0.0920   Median :-0.07666   Median : 0.06296  
#>  Mean   : 0.0000   Mean   : 0.0000   Mean   : 0.00000   Mean   : 0.00000  
#>  3rd Qu.: 0.6269   3rd Qu.: 0.9159   3rd Qu.: 0.44666   3rd Qu.: 0.06296  
#>  Max.   : 5.2569   Max.   : 2.6667   Max.   : 8.29651   Max.   : 4.74606  
#>      screen            ads         
#>  Min.   :-0.615   Min.   :-2.3880  
#>  1st Qu.:-0.615   1st Qu.:-0.4416  
#>  Median :-0.615   Median : 0.2444  
#>  Mean   : 0.000   Mean   : 0.0000  
#>  3rd Qu.: 0.549   3rd Qu.: 0.6273  
#>  Max.   : 2.877   Max.   : 1.5207

3 Map A : Base Compressed Map

This package can perform vector quantization using the following algorithms -

• Hierarchical Vector Quantization using k−means
• Hierarchical Vector Quantization using k−medoids

For more information on vector quantization, refer the following link.

The HVT function constructs highly compressed hierarchical Voronoi tessellations. The raw data is first scaled and this scaled data is supplied as input to the vector quantization algorithm. The vector quantization algorithm compresses the dataset until a user-defined compression percentage/rate is achieved using a parameter called quantization error which acts as a threshold and determines the compression percentage. It means that for a given user-defined compression percentage we get the ‘n’ number of cells, then all of these cells formed will have a quantization error less than the threshold quantization error.

Let’s try to comprehend the HVT function first before moving ahead.

HVT(
  dataset,
  min_compression_perc,
  n_cells,
  depth,
  quant.err,
  distance_metric = c("L1_Norm", "L2_Norm"),
  error_metric = c("mean", "max"),
  quant_method = c("kmeans", "kmedoids"),
  normalize = TRUE,
  diagnose = FALSE,
  hvt_validation = FALSE,
  train_validation_split_ratio = 0.8
)

Each of the parameters have been explained below :

• dataset - A dataframe with numeric columns

• min_compression_perc - An integer indicating the minimum percent compression rate to be achieved for the dataset

• n_cells - An integer indicating the number of cells per hierarchy (level)

• depth - An integer indicating the number of levels. (1 = No hierarchy, 2 = 2 levels, etc …)

• quant.error - A number indicating the quantization error threshold. A cell will only breakdown into further cells if the quantization error of the cell is above the defined quantization error threshold

• distance_metric - The distance metric can be L1_Norm or L2_Norm. L1_Norm is selected by default. The distance metric is used to calculate the distance between an n dimensional point and centroid. The user can also pass a custom function to calculate this distance

• error_metric - The error metric can be mean or max. max is selected by default. max will return the max of m values and mean will take mean of m values where each value is a distance between a point and centroid of the cell. Moreover, the user can also pass a custom function to calculate the error metric

• quant_method - The quantization method can be kmeans or kmedoids. kmeans is selected by default

• normalize - A logical value indicating whether the columns in your dataset need to be normalized. Default value is TRUE. The algorithm supports Z-score normalization

• diagnose - A logical value indicating whether user wants to perform diagnostics on the model. Default value is TRUE.

• hvt_validation - A logical value indicating whether user wants to holdout a validation set and find mean absolute deviation of the validation points from the centroid. Default value is FALSE.

• train_validation_split_ratio - A numeric value indicating train validation split ratio. This argument is only used when hvt_validation has been set to TRUE. Default value for the argument is 0.8

We will use the HVT function to compress our data while preserving essential features of the dataset. Our goal is to achieve data compression upto atleast 80%. In situations where the compression ratio does not meet the desired target, we can explore adjusting the model parameters as a potential solution. This involves making modifications to parameters such as the quantization error threshold or increasing the number of cells and then rerunning the HVT function again.

In our example we will iteratively increase the number of cells until the desired compression percentage is reached instead of increasing the quantization threshold because it may reduce the level of detail captured in the data representation

First, we will construct map A by using the below mentioned model parameters.

Model Parameters

• Number of Cells at each Level = 450
• Maximum Depth = 1
• Quantization Error Threshold = 0.2
• Error Metric = Max
• Distance Metric = Manhattan

map_A <- list()
map_A <-muHVT::HVT(trainComputers,
                n_cells = 450,
                quant.err = 0.2,
                depth = 1,
                distance_metric = "L1_Norm",
                error_metric = "max",
                quant_method = "kmeans",
                normalize = F
)

As per the manual, map_A[[3]] gives us detailed information about the hierarchical vector quantized data. map_A[[3]][['summary']] gives a nice tabular data containing no of points, Quantization Error and the codebook.

The datatable displayed below is the summary from map A

summaryTable(map_A[[3]]$summary,scroll = T,limit = 500)

Now let us understand what each column in the above table means:

• Segment.Level - Level of the cell. In this case, we have performed Vector Quantization for depth 1. Hence Segment Level is 1

• Segment.Parent - Parent segment of the cell

• Segment.Child (Cell.Number) - The children of a particular cell. In this case, it is the total number of cells at which we achieved the defined compression percentage

• n - No of points in each cell

• Cell.ID - Cell_ID’s are generated for the multivariate data using 1-D Sammon’s Projection algorithm

• Quant.Error - Quantization Error for each cell

All the columns after this will contain centroids for each cell. They can also be called a codebook, which represents a collection of all centroids or codewords.

Now, let’s check the compression summary for HVT (map A). The table below shows no of cells, no of cells having quantization error below threshold and percentage of cells having quantization error below threshold for each level.

mapA_compression_summary <- map_A[[3]]$compression_summary %>%  dplyr::mutate_if(is.numeric, funs(round(.,4)))
compressionSummaryTable(mapA_compression_summary)

As it can be seen from the table above, 82% of the cells have hit the quantization threshold error.Since we are successfully able to attain the desired compression percentage, so we will not further subdivide the cells

Now let’s try to understand plotHVT function. The parameters have been explained in detail below

plotHVT(hvt.results, line.width, color.vec, pch1 = 21, centroid.size = 3, title = NULL, maxDepth = 1)

• hvt.results - A list containing the output of the HVT function which has the details of the tessellations to be plotted

• line.width - A vector indicating the line widths of the tessellation boundaries for each layer

• color.vec - A vector indicating the colors of the tessellations boundaries at each layer

• pch1 - Symbol type of the centroids of the tessellations (parent levels). Refer points (default = 21)

• centroid.size - Size of centroids of first level tessellations (default = 3)

• title - Set a title for the plot (default = NULL)

Let’s plot the Voronoi tessellation for layer 1 (map A)

muHVT::plotHVT(map_A,
        line.width = c(0.4), 
        color.vec = c("#141B41"),
        centroid.size = 0.01,
        maxDepth = 1) 

Figure 1: The Voronoi Tessellation for layer 1 (map A) shown for the 450 cells in the dataset ’computers’

We will now overlay all the features as heatmap over the Voronoi Tessellation plot for better visualization and identification of patterns, trends, and variations in the data.

Let’s have a look at the function hvtHmap that we will use to overlay features as heatmap.

hvtHmap(hvt.results, dataset, child.level, hmap.cols, color.vec ,line.width, palette.color = 6)

• hvt.results - A list of results obtained from the HVT function (map_A)

• dataset - A dataframe containing the variables to overlay as a heatmap. The user can pass an external dataset or the dataset that was used to perform hierarchical vector quantization. The dataset should have the same number of points as the dataset used to perform hierarchical Vector Quantization in the HVT function

• child.level - A number indicating the level for which the heat map is to be plotted

• hmap.cols - The column number of column name from the dataset indicating the variables for which the heat map is to be plotted. To plot the quantization error as heatmap, pass 'quant_error'. Similarly to plot the no of points in each cell as heatmap, pass 'no_of_points' as a parameter

• color.vec - A color vector such that length(color.vec) = child.level (default = NULL)

• line.width - A line width vector such that length(line.width) = child.level (default = NULL)

• palette.color - A number indicating the heat map color palette. 1 - rainbow, 2 - heat.colors, 3 - terrain.colors, 4 - topo.colors, 5 - cm.colors, 6 - BlCyGrYlRd (Blue,Cyan,Green,Yellow,Red) color (default = 6)

• show.points - A boolean indicating whether the centroids should be plotted on the tessellations (default = FALSE)

Now let’s plot the Voronoi Tessellation with the heatmap overlaid for all the features in the torus data for better visualization and interpretation of data patterns and distributions.

The heatmaps displayed below provides a visual representation of the spatial characteristics of the computers data, allowing us to observe patterns and trends in the distribution of each of the features (price,speed,hd,ram,screen,ads). The sheer green shades highlight regions with higher values in each of the heatmaps, while the indigo shades indicate areas with the lowest values in each of the heatmaps. By analyzing these heatmaps, we can gain insights into the variations and relationships between each of these features within the computers data

  hvtHmap(
  map_A,
  scores,
  child.level = 1,
  hmap.cols = "price",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.1,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 450,
) 

Figure 2: The Voronoi Tessellation with the heat map overlaid for variable ’price’ in the ’computers’ dataset

  hvtHmap(
  map_A,
  scores,
  child.level = 1,
  hmap.cols = "speed",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.1,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 450,
) 

Figure 3: The Voronoi Tessellation with the heat map overlaid for variable ’speed’ in the ’computers’ dataset

  hvtHmap(
  map_A,
  scores,
  child.level = 1,
  hmap.cols = "hd",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.1,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 450,
) 

Figure 4: The Voronoi Tessellation with the heat map overlaid for variable ’hd’ in the ’computers’ dataset

  hvtHmap(
  map_A,
  scores,
  child.level = 1,
  hmap.cols = "ram",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.1,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 450,
) 

Figure 5: The Voronoi Tessellation with the heat map overlaid for variable ’ram’ in the ’computers’ dataset

  hvtHmap(
  map_A,
  scores,
  child.level = 1,
  hmap.cols = "screen",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.1,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 450,
) 

Figure 6: The Voronoi Tessellation with the heat map overlaid for variable ’screen’ in the ’computers’ dataset

  hvtHmap(
  map_A,
  scores,
  child.level = 1,
  hmap.cols = "ads",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 0.1,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 450,
) 

Figure 7: The Voronoi Tessellation with the heat map overlaid for variable ’ads’ in the ’computers’ dataset

4 Map B : Compressed Novelty Map

In this section, we will manually figure out the novelty cells from the plotted map A and store it in identified_Novelty_cells variable.

The removeNovelty function removes the identified novelty cell(s) from the dataset and stores those records separately.

It takes input as the cell number (Segment.Child) of the manually identified novelty cell(s) from the above table and the compressed HVT map (map A). It returns a list of two items: dataset with novelty records, and a subset of the dataset without the novelty records.

identified_Novelty_cells <<- c(35,262,318)
output_list <- removeNovelty(identified_Novelty_cells, map_A)

[1] “The following cell(s) have been removed as outliers from the dataset: 35 262 318”

data_with_novelty <- output_list[[1]]
dataset_without_novelty <- output_list[[2]]

Note - In the dataset with novelty, the total number of cells would be equal to the total number of novelty cell(s) removed from the HVT map A. Let’s say, as in the above case where three cells (35th, 262nd, and 318th) are identified as the novelty and are removed. Then the 35th cell would be the first cell in the HVT map B, 262th as the second cell, and 318th as the third cell.

Let’s have a look at the data with novelties.For the sake of brevity, we will only show the first 10 rows

colnames(data_with_novelty) <- c("Cell.ID","Segment.Child","price","speed","hd","ram","screen","ads")
data_with_novelty %>% head(100) %>% 
  as.data.frame() %>%
  Table(scroll = T, limit = 20)

4.1 Voronoi tessellation to highlight novelty cell in the map

The plotCells function is used to plot the Voronoi tessellation using the compressed HVT map (map A) and highlights the identified novelty cell(s) in red on the map.

plotCells(identified_Novelty_cells, map_A,line.width = c(0.4),centroid.size = 0.01)

Figure 8: The Voronoi Tessellation constructed using the compressed HVT map (map A) with the novelty cell(s) highlighted in red

We pass the dataframe with novelty records to HVT function along with other model parameters mentioned below to generate map B (layer2)

Model Parameters

• Number of Cells at each Level = 3
• Maximum Depth = 1
• Quantization Error Threshold = 0.2
• Error Metric = Max
• Distance Metric = Manhattan

dataset_with_novelty <- data_with_novelty[,-1:-2]
map_B <- list()
map_B <- muHVT::HVT(dataset_with_novelty,
                  n_cells = 3,
                  depth = 1,
                  quant.err = 0.2,
                  projection.scale = 10,
                  normalize = F,
                  distance_metric = "L1_Norm",
                  error_metric = "max",
                  quant_method = "kmeans",
                  diagnose = F)

The datatable displayed below is the summary from map B (layer 2)

summaryTable(map_B[[3]]$summary,scroll = T,limit = 500)

Segment.Level	Segment.Parent	Segment.Child	n	Cell.ID	Quant.Error	price	speed	hd	ram	screen	ads
1	1	1	15	2	0.07	0.66	-0.78	0.82	1.62	-0.61	0.31
1	1	2	10	1	0.17	0.73	-0.78	-0.54	-0.09	2.88	-2.18
1	1	3	16	3	0.09	0.68	-0.78	0.84	1.62	-0.61	0.82

5 Map C : Compressed Map without Novelty

With the Novelties removed, we construct another hierarchical Voronoi tessellation map C layer 2 on the dataset without Novelty and below mentioned model parameters.

Model Parameters

• Number of Cells at each Level = 100
• Maximum Depth = 2
• Quantization Error Threshold = 0.2
• Error Metric = Max
• Distance Metric = Manhattan

map_C <- list()
map_C <- muHVT::HVT(dataset_without_novelty,
                  n_cells = 100,
                  depth = 2,
                  quant.err = 0.2,
                  projection.scale = 10,
                  normalize = F,
                  distance_metric = "L1_Norm",
                  error_metric = "max",
                  quant_method = "kmeans",
                  diagnose = F)

The datatable displayed below is the summary from map C (layer2)

summaryTable(map_C[[3]]$summary,scroll = T,limit = 500)